Day25 Leetcode Array系列---- Maximum Product Subarray

本次題目 Maximum Product Subarray by js

這次的題目是之前 Maximum Subarray 的變形，這次要的不是大陣列內擁有最大和的小陣列，而是要找乘積最大的小陣列

Example 1:
input1 = [2,3,-2,4]
output1 =  6
// Explanation: [2,3] has the largest product 6.

Example 2:
input2 = [-2,0,-1]
output2 = 0
// Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

思考路線 1

1. 利用雙迴圈取值，這樣可以把陣列中所有會出現的子陣列都跑過一輪
2. 記錄最大的乘積，將目前最大的乘積與每次計算結果都做比較，並把大的值當作最大乘積
3. 要取的大陣列中的小陣列可以用 splice ，可以依據提供的索引範圍取出對應範圍的小陣列，只是要注意取出的範圍並不包含第 2 個參數的元素

//splice
a = [0,1,2,3,4,5,6]
a.splice(0,3) // [0,1,2]        並非 [0,1,2,3]  不包含索引3的元素

4. 可以用 reduce 計算乘積， reduce 能把陣列中的元素轉換成一個值，這邊就讓取出的小陣列所有元素相乘取得乘機

Coding Time

這裡先設定 max 之後算出來的值都會與它比較

建立雙迴圈，內迴圈的範圍會比外迴圈小，這樣可以避免取到同樣的值，減少迴圈圈數

利用兩個迴圈的 i j 當作範圍，搭配 slice 取出大陣列中的小陣列

reduce 去計算乘積

最後比較大小，是目前計算的乘積大還是記錄中的最大乘積大，如果目前計算結果比較大，最大乘積就等於目前計算結果

input1 = [2,3,-2,4]
output1 =  6
// Explanation: [2,3] has the largest product 6.
input2 = [-2,0,-1]
output2 = 0
// Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

function maximumProduct(ary){
  let max = 0
  for(let i = 0; i < ary.length; i++ ){
    for(let j = i+1; j < ary.length; j++){
      let temp = ary.slice(i,j+1).reduce( ( acc,num )=> { return acc*num},1 )
      
      max = Math.max(max,temp)
    }
  } 
  return max
}

function expect(a,b){
  console.log(a==b)
}

expect(maximumProduct(input1),output1)
expect(maximumProduct(input2),output2)

思考路線 2

1. 用單迴圈就可以了
2. 需要紀錄最大乘積與連續乘積結果，每圈都會比較最大乘積與連續乘積的大小，保留最大值，現有乘積是考慮到負負得正，這時就可以拿負負得正的結果與最大乘積做比較
3. 考慮陣列中會不會有 0 ，如果有就要重設 連續乘積，因為所有數字乘上 0 都是 0

Coding Time

input1 = [2,3,-2,4]
output1 =  6
// Explanation: [2,3] has the largest product 6.
input2 = [-2,0,-1]
output2 = 0
// Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

function maximumProduct(ary){
  let max = 0
  let current = 1
  for( let i = 0; i < ary.length; i++ ){
    current = current * ary[i]
    
    if( max < current){
      max = current
    }

    if( ary[i] === 0){ //陣列中有 0 就須要重設 current
      current = 1
    }
  }
  return max
}

function expect(a,b){
  console.log(a===b)
}

expect(maximumProduct(input1),output1)
expect(maximumProduct(input2),output2)

今天到此為止，有任何問題請在下方留言或透過email、GitHub聯絡我，感謝閱讀

Daily kitty